from difflib import SequenceMatcher
from random import choice, randrange
import string
import sys

class Fuzzer:
    """
    This simple class is responsible for generating random inputs and matching input pairs.
    """
    def __init__(self, alphabet=string.printable, equalizeCoverage=False):
        """
        @param equalizeCoverage: if set to True, the fuzzer will try to choose the passing input 
        to produce a run with the most similar coverage to the failing run, 
        otherwise, the fuzzer will govern its choice by the similarities between the inputs.
        """
        self.__alpha = alphabet
        self.__equalizeCoverage = equalizeCoverage
        
    def getNext(self, length=15, joiner=''):
        assert length > 0
        assert joiner is not None
        alpha = self.__alpha
        return joiner.join(choice(alpha)for _ in xrange(length))
    
    def ddmin(self, func, s):
        """
        Standard delta minimizer.
        """
        assert func(s) == 'FAIL'
        n = 2
        while len(s) >= 2:
            start = 0
            subset_length = len(s) // n
            some_complement_is_failing = False
            while start < len(s):
                complement = s[:start] + s[start + subset_length:]
                if func(complement) == 'FAIL':
                    s = complement
                    n = max(n - 1, 2)
                    some_complement_is_failing = True
                    break
                start += subset_length
            if not some_complement_is_failing:
                if n == len(s):
                    break
                n = min(n * 2, len(s))
        return s
    
    def __record_coverage(self, cov, frame, event, arg):
        if event == 'line':
            cov.append(frame.f_lineno)
        return lambda f, e, a: self.__record_coverage(cov, f, e, a)
    
    def __ddminCov(self, func, oracle, s):
        """
        @requires: s induces failure in func
        @requires: oracle takes (input, delivered output) and returns 'FAIL' or 'PASS'
        This variant only minimizes the input, if the coverage remains relatively similar.
        @return: a tuple of the form: 
                minimized faiure inducing input, its coverage
        """
        coverageOriginal = []
        coverageLatest = []
        sys.settrace(lambda f, e, a:self.__record_coverage(coverageOriginal, f, e, a))
        delivered = func(s)
        sys.settrace(None)
        assert oracle(s, delivered) == 'FAIL'
        m = SequenceMatcher(None, '', coverageOriginal, False)
        threshold = .6
        n = 2
        while len(s) >= 2:
            start = 0
            subset_length = len(s) // n
            some_complement_is_failing = False
            while start < len(s):
                complement = s[:start] + s[start + subset_length:]
                delivered = func(complement)
                if oracle(complement, delivered) == 'FAIL':
                    coverageComplement = []
                    sys.settrace(lambda f, e, a:self.__record_coverage(coverageComplement, f, e, a))
                    func(complement)
                    sys.settrace(None)
                    m.set_seq1(coverageComplement)
                    if m.quick_ratio() > threshold and m.ratio() > threshold:
                        s = complement
                        coverageLatest = coverageComplement[:]
                        n = max(n - 1, 2)
                        some_complement_is_failing = True
                        break
                start += subset_length
            if not some_complement_is_failing:
                if n == len(s):
                    break
                n = min(n * 2, len(s))
        return s, coverageLatest
    
    def __findFailing(self, func, oracle, length, limit):
        failing = None
        for _ in xrange(limit):
            inp = self.getNext(length)
            delivered = func(inp)
            if oracle(inp, delivered) == 'FAIL':
                failing = inp
                break
        return failing
    
    def __findPassingCov(self, failing, failCov, func, oracle, limit):
        mCov = SequenceMatcher(None, '', failCov, False)
        mInp = SequenceMatcher(None, '', failing, False)
        thresholdCov = .97
        passing = None
        passCov = None
        best = 0
        bestI = 0
        for _ in xrange(limit):
            inp = self.getNext(len(failing) + randrange(5))
            delivered = func(inp)
            if oracle(inp, delivered) != 'FAIL':
                cov = []
                sys.settrace(lambda f, e, a:self.__record_coverage(cov, f, e, a))
                func(inp)
                sys.settrace(None)
                mCov.set_seq1(cov)
                if (mCov.real_quick_ratio() >= best) and (mCov.quick_ratio() >= best):
                    score = mCov.ratio()
                    mInp.set_seq1(inp)
                    scoreI = mInp.ratio()
                    if score > best:
                        best = score
                        passing = inp
                        bestI = scoreI
                        passCov = cov[:]
                        if best > thresholdCov:  # THRESHOLD REACHED
                            break
                    elif score == best:
                        if scoreI > bestI:  # REFINING MATCH
                            passing = inp
                            bestI = scoreI
                            passCov = cov[:]
        return passing, passCov
    
    def __findPassing(self, failing, func, oracle, limit):
        m = SequenceMatcher(None, '', failing, False)
        threshold = .8
        passing = None
        passCov = None
        best = 0
        for _ in xrange(limit):
            inp = self.getNext(len(failing) + randrange(5))
            if oracle(inp, func(inp)) != 'FAIL':
                m.set_seq1(inp)
                if (m.real_quick_ratio() > best) and (m.quick_ratio() > best):
                    score = m.ratio()
                    if score > best:
                        best = score
                        passing = inp
                        if best > threshold:
                            break
        if passing:
            passCov = []
            sys.settrace(lambda f, e, a:self.__record_coverage(passCov, f, e, a))
            func(passing)
            sys.settrace(None)
        return passing, passCov
    
    def getNextPair(self, func, oracle, length=15, limit=32768):
        """
        @return: a tuple of the form (failingInput, passingInput, failingCoverage, passingCoverage)         
        """
        assert length > 0
        assert limit > 0
        # step 1: find a failing input
        failing = self.__findFailing(func, oracle, length, limit)
        if failing is None:  # couldn't find a failing input
            return (None, None, None, None)
        # step 2: minimize it
        if self.__equalizeCoverage:
            failing, failCov = self.__ddminCov(func, oracle, failing)  # only minimizes if coverage remains similar
        else:
            failing = self.ddmin(lambda s:oracle(s, func(s)), failing)  # use standard ddmin
            # record coverage of the minimized failrun manually
            failCov = []
            sys.settrace(lambda f, e, a:self.__record_coverage(failCov, f, e, a))
            func(failing)
            sys.settrace(None)
        # step 3: find a similar passing input
        if self.__equalizeCoverage:
            passing, passCov = self.__findPassingCov(failing, failCov, func, oracle, limit)
        else:
            passing, passCov = self.__findPassing(failing, func, oracle, limit)
        return (failing, passing, failCov, passCov)
        
# for testing purposes
if __name__ == '__main__':
    f = Fuzzer(string.letters + string.digits)
    for L in xrange(1, 41):
        print L, f.getNext(L)
